package nowcoder.written_examination.wangyi;

import common.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author fance
 * @date 18-7-2 下午1:03
 */
public class MainVI {
    public static void main(String[] args) {

    }
    private  boolean reachable = false;
    public int cmp(int g1, int g2, int[][] records, int n) {
        // write code here
        HashMap<Integer, List<Integer>> map = generateMap(records, n);
        if (map.isEmpty()) {
            return 0;
        }
        depthSearch(g1, g2, map);
        if (reachable) {
            return 1;
        }
        depthSearch(g2, g1, map);
        if (reachable) {
            return -1;
        }
        return 0;
    }
    private void depthSearch(int g1, int g2, HashMap<Integer, List<Integer>> map) {
        if (!map.containsKey(g1)) {
            reachable = false;
        } else {
            List<Integer> values = map.get(g1);
            for (int value : values) {
                if (g2 == value) {
                    reachable = true;
                    return;
                } else {
                    depthSearch(value, g2, map);
                }
            }

        }
    }

    public HashMap<Integer, List<Integer>> generateMap(int[][] records, int n) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int key = records[i][0];
            int value = records[i][1];
            if (map.containsKey(key)) {
                map.get(key).add(value);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(value);
                map.put(key, list);
            }
        }
        return map;
    }
    public int getDis(TreeNode root) {
        // write code here
        int  max = findMax(root);
        int  mid = findMin(root);
        return 0;
    }
    private int findMax(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(root.val,Math.max(findMax(root.left),findMax(root.right)));
    }
    private int findMin(TreeNode root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        return Math.min(root.val,Math.min(findMin(root.left),findMin(root.right)));
    }
    public int findKth(int[] a, int n, int K) {
        // write code here
        K = a.length - K;
        int lo = 0;
        int hi = a.length - 1;
        while (lo < hi) {
            int j = partition(a,lo,hi);
            if (j < K) {
                lo = j + 1;
            } else if (j > K) {
                hi = j - 1;
            } else {
                break;
            }
        }
        return a[K];
    }
    int partition(int[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        int v = a[lo];
        while (true) {
            while (a[++i] < v) {
                if (i == hi) {
                    break;
                }
            }
            while (a[--j] > v) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            swap(a,i,j);
        }
        swap(a,lo,j);
        return j;
    }
    void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

class Tree {
    private int max = 0;
    private int min = 99999;
    private StringBuilder maxcodec;
    private StringBuilder mincodec;

    void PreOrder(TreeNode T, char code, StringBuilder codec) {
        if (T != null) {
            codec.append(code);
            if (T.left == null && T.right == null) {
                if (max < T.val) {
                    max = T.val;
                    maxcodec = codec;
                }

                if (min > T.val) {
                    min = T.val;
                    mincodec = codec;
                }
            }
            PreOrder(T.left, '0', new StringBuilder(codec));
            PreOrder(T.right, '1', new StringBuilder(codec));
        }
    }

    public int getDis(TreeNode root) {
        PreOrder(root, '0', new StringBuilder());
        int index = 0;
        for (index = 0; index < (maxcodec.length() > mincodec.length() ? maxcodec.length() : mincodec.length()); index++) {
            if (maxcodec.charAt(index) != mincodec.charAt(index)) {
                break;
            }
        }
        return (maxcodec.substring(index).length() + mincodec.substring(index).length());

        // write code here
    }


    class Tree2 {

        private TreeNode maxNode = new TreeNode(Integer.MIN_VALUE);

        private TreeNode minNode = new TreeNode(Integer.MAX_VALUE);


        public int getDis(TreeNode root) {

            // write code here

            getMaxMin(root);//找到最大最小叶子节点

            TreeNode lcaNode = getLCA(root);//找LCA

            int a = getNodeDis(lcaNode, maxNode);//最大值叶子节点到LCA的距离；

            int b = getNodeDis(lcaNode, minNode);//最小值叶子节点到LCA的距离；

            return a + b;

        }


// 先找到最大最小叶子节点

        public void getMaxMin(TreeNode root) {

            if (root == null) {

                return;

            }

            if (root.left == null && root.right == null) {

                if (root.val > maxNode.val) {

                    maxNode = root;

                } else if (root.val < minNode.val) {

                    minNode = root;

                }

            }

            getMaxMin(root.left);

            getMaxMin(root.right);

        }


// LCA最近公共祖先

        public TreeNode getLCA(TreeNode root) {

            if (root == null) {// 说明是空树

                return null;

            }

            if (root.val == maxNode.val || root.val == minNode.val) {// 在当前树的根节点上找到两个节点之一

                return root;

            }

            TreeNode leftNode = getLCA(root.left);// 左子树中的查找两个节点并返回查找结果

            TreeNode rightNode = getLCA(root.right);// 右子树中查找两个节点并返回查找结果

            if (leftNode == null) {// 左子树中没找到，则一定在右子树上

                return rightNode;

            } else if (rightNode == null) {// 右子树没找到一定在左子树上

                return leftNode;

            } else {// 左右子树均找到一个节点，则根节点为最近公共祖先

                return root;

            }

        }


//获取叶子节点到LCA距离

        public int getNodeDis(TreeNode lcaNode, TreeNode node) {

            if (lcaNode == null) {

                return -1;

            }

            if (lcaNode.val == node.val) {

                return 0;

            }

            //三种情况：两个均在左子树；两个均在右子树；一左一右，所以不能用if-elseif结构

            int distance = getNodeDis(lcaNode.left, node);//左子树未找到两个节点之一

            if (distance == -1) {

                distance = getNodeDis(lcaNode.right, node);

            }

            if (distance != -1) {

                return distance + 1;

            }


            return -1;

        }
    }
}
